1540. 23 out of 5
Is it possible to find an
arithmetic expression consisting of five given numbers that will yield the
value 23. For this problem you can use only three arithmetic expressions: +,
-, *. Assume that all these operations have the same priority and executed
sequentially from left to right.
Input.
Each line contains five positive integers from 1 to 50. Input is
terminated by a line containing five zero’s and is not processed.
Output. For each test case print “Possible” (without quotes) if their exists
an arithmetic expression as described above that yields 23. Otherwise
print “Impossible”.
|
Sample input |
Sample output |
|
1 1 1
1 1 1 2 3
4 5 2 3 5
7 11 0 0 0
0 0 |
Impossible Possible Possible |
combinatorics – backtracking
Generate all
permutations of input numbers. For each permutation between the numbers place
all possible signs of arithmetic operations and calculate the resulting
expressions. If at least one expression has the value of 23, then set the
variable flag to 1 and end the
processing of the current test.
Store the input
five numbers in an integer array a. The variable flag takes the value of 1 if an expression with the value 23 is found, otherwise flag = 0.
int a[5], flag;
Function RunSum evaluates the value of an
expression which
operands are in array a. The signs of various operations are inserted between
the operands and the resulting expressions are computed using the backtracking technique. If the value of one of expressions is 23,
then function returns 1, otherwise 0.
int
RunSum(int Sum, int
index)
{
if (index ==
5)
if (Sum ==
23) return 1; else
return 0;
if
(RunSum(Sum+a[index],index+1)) return 1;
if
(RunSum(Sum-a[index],index+1)) return 1;
if
(RunSum(Sum*a[index],index+1)) return 1;
return 0;
}
The main part of the program.
Read five numbers
into array a. Start the
procedure for generating all permutations. Since the next_permutation function
generates permutations in lexicographic order, the smallest permutation must be
the first. The smallest permutation is the one in which the numbers form a
non-decreasing sequence. That is, before generating the permutations, the
numbers in the array a should be
sorted in non decreasing
order (if this is not done, then not all permutations will be considered).
while(scanf("%d %d %d %d %d",
&a[0],&a[1],&a[2],&a[3],&a[4]),a[0]+a[1]+a[2]+a[3]+a[4])
{
sort(a,a+5);
flag = 0;
do{
For each
permutation, run the RunSum function, which finds out
whether it is possible to arrange the operation signs between the numbers of
this permutation so as to obtain the value 23.
if (flag =
RunSum(a[0],1)) break;
} while(next_permutation(a,a+5));
If the variable flag is set to 1, then print “Possible”, otherwise print “Impossible”.
if (flag)
printf("Possible\n"); else printf("Impossible\n");
memset(a,0,sizeof(a));
}